/*
 * @lc app=leetcode.cn id=42 lang=cpp
 *
 * [42] 接雨水
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    int trap(vector<int>& height) {
        // DP left / right to get intersection
        // two pointer

        // single stack
        // 栈中的元素要么递增, 要么递降, 如果有新的元素不满足这个特点
        // , 就不断的将栈顶元素出栈, 直到满足为止
        // stack<int : index>
        ;
    }
};
class SolutionViolent {
public:
    int trap(vector<int>& height) {
        int localHeight = 0;
        int localIndex = 0;

        int globalMaximum = 0;
        int globalMaxIndex = 0;
        int globalMaxPairIndex = 0;

        bool increasing = true;

        // <height, left index>
        std::vector<std::pair<int, int>> localMax;
        // searching local maximum value

        for (int i=0;i<height.size();i++){
            if (increasing){
                if (height[i] > localHeight){
                    localHeight = height[i];
                    localIndex = i;
                }
                // == : index still left edge
                else if(height[i] < localHeight){
                    increasing = false;

                    if (localHeight > globalMaximum){
                        globalMaximum = localHeight;
                        globalMaxIndex = localIndex;
                        globalMaxPairIndex = localMax.size();
                    }
                    localMax.emplace_back(localHeight, localIndex);
                    localHeight = height[i];
                }
            }
            else {
                if (height[i] < localHeight){
                    localHeight = height[i];
                }
                // == : still left
                else if (height[i] > localHeight){
                    increasing = true;
                    localHeight = height[i];
                    localIndex = i;
                }
            }
        }
        if (increasing){
            if (localHeight > globalMaximum){
                globalMaximum = localHeight;
                globalMaxIndex = localIndex;
                globalMaxPairIndex = localMax.size();
            }
            localMax.emplace_back(localHeight, localIndex);
        }

        // for (auto& pair : localMax){
        //     printf("(%d %d) ", pair.first, pair.second);
        // }
        // printf(" global %d %d\n", globalMaximum, globalMaxIndex);

        // find global maximum
        // than go left / right for second maximum
        // than from left second go left third ...

        globalMaxIndex;

        int sum = 0;

        goLeft(globalMaxPairIndex, sum, localMax, height);
        goRight(globalMaxPairIndex, sum, localMax, height);

        return sum;
    }
private:
    inline void goLeft( 
                int maxPairIndex,
                int & sum,
                std::vector<std::pair<int, int>>& localMax,
                vector<int>& heights){
        int leftIndex = 0;
        int leftPairIndex = 0;
        int leftHeight = 0;
        for (int i=0;i<maxPairIndex;i++){
            if (localMax[i].first > leftHeight){
                leftIndex = localMax[i].second;
                leftPairIndex = i;
                leftHeight = localMax[i].first;
            }
        }
        if (leftHeight == 0){
            return;
        }
        sum += sumWater(leftIndex, localMax[maxPairIndex].second,
                        std::min(leftHeight, localMax[maxPairIndex].first), 
                        heights);
// printf("now sum = %d\n", sum);
        goLeft(leftPairIndex, sum, localMax, heights);
    }
    inline void goRight( 
                int maxPairIndex,
                int & sum,
                std::vector<std::pair<int, int>>& localMax,
                vector<int>& heights){
        int rightIndex = 0;
        int rightPairIndex = 0;
        int rightHeight = 0;
        for (int i=localMax.size()-1;i>maxPairIndex;i--){
            if (localMax[i].first > rightHeight){
                rightIndex = localMax[i].second;
                rightPairIndex = i;
                rightHeight = localMax[i].first;
            }
        }
        if (rightHeight == 0){
            return;
        }
        sum += sumWater(localMax[maxPairIndex].second, rightIndex,
                        std::min(rightHeight, localMax[maxPairIndex].first), 
                        heights);
// printf("now sum = %d\n", sum);
        goRight(rightPairIndex, sum, localMax, heights);
    }
    inline int sumWater(int left, int right, int height, vector<int>& heights){
        int sum = 0;
        for (int i=left+1;i<right;i++){
            if (heights[i] >= height){continue;}
            sum += height-heights[i];
        }
        return sum;
    }
};
// @lc code=end

int main(){
    vector<int>height = {5,4,1,2};
    Solution test;
    test.trap(height);
}